1. Technical Field
The present invention relates generally to the processing of data and in particular to a multi-processor data processing system. Still more particularly, the present invention relates to a method and apparatus for handling queues in a multiprocessor data processing system.
2. Description of the Related Art
Multiprocessor data processing systems contain multiple processors that each can operate on its own data. Typically, these processors operate independently of each other, normally on autonomous tasks or significant portions of large tasks. Multiprocessor systems typically fall into two categories: shared-memory systems and distributed-memory systems. In shared memory systems, the processors communicate by reading and writing data to a shared memory location in a common address space. Additionally, shared memory usually implies a shared bus, but such is not necessarily the case. Within the shared memory, communications between various processors are usually performed through queues. Typically, a large number of queues are commonly used by the data processing system to control reusable hardware and software resources within the data processing system, including the queues, which are themselves system resources.
Queues are data structures used to organize sets of data blocks in memory by means of pointers associated with each data block in a queue. Each queue typically includes a number of entries, also called "elements," with each entry or element comprising a unit of the queue. Queues may be classified into several general types according to the relative locations of the elements in the queue. Contiguous queues have elements physically located next to each other while linear chained queues are queues with elements physically disbursed anywhere within main or virtual storage.
The data blocks within queues, whether located physically next to each other or disbursed within main or virtual storage, are associated with each other through linked lists. A "doubly linked" list has two pointers in each element, pointing to the next and previous elements in the list. In the case of "singly linked" queues, the pointers reference the addresses of successive data blocks in the queue. A singly linked queue is a queue in which each element includes a pointer to its successor in the queue.
Data processing systems with multiple processing units coupled to a memory system often perform queued operations to organize related blocks of stored data. In particular, multiprocessor designs that consist of one or more main processors and an input/output (I/O) sub-processor commonly utilize shared queues in system memory to allow each main processor to communicate with the I/O sub-processor. An output queue, also called a "start" queue, is employed to send I/O requests from the main processor to the sub-processor. Similarly, an input queue, also called a "completion" queue, is employed to return completion information from the sub-processor to the main processor. In both cases, one processor adds an item to the queue by a "post" operation while the other processor removes an item from the queue by a "clear" operation. Thus, both the main processor and the sub-processor must be capable of performing read-modify-write operations on the queues.
In data processing systems having multiple central processors, each simultaneously and asynchronously executing separate instruction streams relative to a shared memory system, queue integrity is a serious concern. It is undesirable for a processor to take action based on a change in the queue by another processor which is not yet complete. This could happen, for example, if one processor attempts to change a queue element while another processor is changing that element. In open platform systems, in particular, read-modify-write operations are not guaranteed to be atomic, which means that it is possible for one processor to alter shared memory during a modify phase in another processor.
To maintain queue integrity, queues in shared memory systems have a mutual exclusion requirement during certain read-modify-write operations. Existing designs that use queues in shared memory rely on software locking mechanisms to enforce this mutual exclusion. Because such locking mechanisms degrade I/O performance by introducing latency (delay) in both the main processor and I/O sub-processor operations, it is desirable to eliminate the lock requirement. The latency introduced by locking mechanisms becomes especially important if the I/O sub-processor has limited processing capability relative to the main processor. Whenever a lock occurs, execution in one processor stalls until the other processor releases the lock. Thus, in cases where the capability of the sub-processor is limited, the performance degradation of the main processor is disproportionate to that of the sub-processor.
It would be advantageous to increase the total number of I/O operations completed during a given unit of time by a typical data processing system. The mechanism employed should be applicable to any system using one or more main processors handling upper level operating system operations and one or more independent I/O sub-processors handling lower level transport I/O protocol(s).